package org.example.algorithm.rabinkarp;
/**
 * 字符串匹配问题：
 * 1) 有一个字符串 str1= ""硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好""，和一个子串 str2="尚硅谷你尚硅你"
 * 2) 现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1
 * 3) 要求用最快的速度来完成匹配，请用Java代码实现
 * 字符串匹配算法：Rabin-Karp算法——利用哈希值来进行模式匹配。
 *
 */
public class RabinKarp {
    private static final int BASE = 26; // 假设字符集为小写字母

    public static int rabinKarpSearch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int patternHash = hash(pattern);
        int textHash = hash(text.substring(0, m));

        for (int i = 0; i <= n - m; i++) {
            if (patternHash == textHash && compareStrings(i, text, pattern)) {
                return i;
            }
            if (i < n - m) {
                textHash = nextHash(text, textHash, i, m);
            }
        }
        return -1;
    }

    private static int hash(String str) {
        int hash = 0;
        for (char c : str.toCharArray()) {
            hash = (hash * BASE + (c - 'a')) % Integer.MAX_VALUE;
        }
        return hash;
    }

    private static int nextHash(String text, int currentHash, int index, int m) {
        currentHash = (currentHash - (text.charAt(index) - 'a') * pow(BASE, m - 1)) % Integer.MAX_VALUE;
        currentHash = (currentHash * BASE + (text.charAt(index + m) - 'a')) % Integer.MAX_VALUE;
        return currentHash;
    }

    private static boolean compareStrings(int index, String text, String pattern) {
        String temp = text.substring(index, index + pattern.length());
        return temp.equals(pattern);
    }

    private static int pow(int base, int exp) {
        int result = 1;
        for (int i = 0; i < exp; i++) {
            result *= base;
        }
        return result;
    }

    public static void main(String[] args) {
        String str1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好";
        String str2 = "尚硅谷你尚硅你";
        int index = rabinKarpSearch(str1, str2);
        System.out.println("第一次出现的位置：" + index);
    }
}
